package com.caochenlei.dynamicProgramming;

import java.util.Scanner;

public class Backpacker2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();              //获取背包容量
        int n = scanner.nextInt();              //获取物品数量
        int[] w = new int[n + 1];               //定义重量数组
        int[] c = new int[n + 1];               //定义价值数组
        int[] dp = new int[m + 1];              //存储中间结果

        for (int i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();           //接收物品重量
            c[i] = scanner.nextInt();           //接收物品价值
        }

        for (int i = 1; i <= n; i++) {          //动态规划处理
            for (int j = m; j >= 1; j--) {
                if (w[i] <= j) {
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);
                }
            }
        }

        System.out.println(dp[m]);              //输出最终结果
    }
}
